package com.leetcode.algorithm.y22.m08.w1;

import java.util.LinkedList;
import java.util.Queue;

import com.leetcode.algorithm.common.TreeNode;

/**
 * 623. 在二叉树中增加一行
 * 
 * https://leetcode.cn/problems/add-one-row-to-tree/
 * 
 * @author jie.deng
 *
 */
class Question0623Solution01 {

	public TreeNode addOneRow(TreeNode root, int val, int depth) {
		if (depth == 1) {
			TreeNode node = new TreeNode(val);
			node.left = root;
			return node;
		}
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		while (depth > 2) {
			int len = queue.size();
			for (int i = 0; i < len; i++) {
				TreeNode node = queue.poll();
				if (node.left != null) {
					queue.offer(node.left);
				}
				if (node.right != null) {
					queue.offer(node.right);
				}
			}
			depth--;
		}
		while (!queue.isEmpty()) {
			TreeNode node = queue.poll();
			TreeNode left = node.left;
			TreeNode right = node.right;
			node.left = new TreeNode(val);
			node.left.left = left;
			node.right = new TreeNode(val);
			node.right.right = right;
		}

		return root;
	}

}